﻿#include<iostream>
using namespace std;
#include<string>
#include<vector>



//实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

//位图思想

//class Solution
//{
//public:
//    bool isUnique(string astr)
//    {
//        if (astr.size() > 26)
//        {
//            return false;
//        }//鸽巢原理
//
//        int ch = 0;
//        for (auto it : astr)
//        {
//            int x = it - 'a';
//            if (((ch >> x) & 1) == 1)//判断第x位是否为1,1代表出现过，因为初始全部为0
//            {
//                return false;
//            }
//            else
//            {
//                ch = ch | (1 << x);
//            }
//        }
//        return true;
//    }
//};


//给定一个包含[0, n] 中 n 个数的数组 nums ，找出[0, n] 这个范围内没有出现在数组中的那个数。

//class Solution
//{
//public:
//    int missingNumber(vector<int>& nums)
//    {
//        int n = nums.size();
//        int x = 0;
//        for (int i = 0; i <= n; ++i)
//        {
//            x ^= i;
//        }
//        for (auto it : nums)
//        {
//            x ^= it;
//        }
//        return x;
//
//    }
//};


//给你两个整数 a 和 b ，不使用 运算符 + 和 - ​​​​​​​，计算并返回两整数之和。

//class Solution
//{
//public:
//    int getSum(int a, int b)
//    {
//        //a^b实质是无进位相加
//        int x = a, y = b;
//        while (b)
//        {
//            x = a ^ b;
//            y = (a & b) << 1;//a&b算出需要进位的地方为1，然后向左移动，重复操作知道b为0
//            a = x, b = y;
//        }
//        return a;
//    }
//};


//给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

class Solution
{
public:
    int singleNumber(vector<int>& nums)
    {
        int n = 0;
        for (int i = 0; i < 32; ++i)
        {
            int sum = 0;//统计该比特位上的总和
            for (auto it : nums)
            {
                if (((it >> i) & 1) == 1)
                {
                    sum++;
                }
            }
            sum %= 3;//因为出现三次的数在此比特位上之和取模3都为0，所以最后为1或者0就是出现一次的数在此比特位上的值
            if (sum == 1)
            {

                n = n | (1 << i);
            }
        }
        return n;
    }
};